package com.zdp.剑指offer;

import com.zdp.util.ListNode;

public class 链表中倒数第k个结点 {
    public static void main(String[] args) {
        链表中倒数第k个结点 demo = new 链表中倒数第k个结点();
        for(int i=10;i<25;i++){
            ListNode p = ListUtil.createList(i);
            ListUtil.outList(p);
            int k =(int)(Math.random()*i)+1;
            ListNode listNode = demo.FindKthToTail1(p, k);
            ListNode listNode2 = demo.FindKthToTail(p,k);
            System.out.println(listNode.val);
            System.out.println(listNode==listNode2);
            System.out.println("===========删除倒数第"+k+"个顶点===========");
        }
    }
    //第一种办法
    public ListNode FindKthToTail1(ListNode head,int k) {
        ListNode result = head;
        int length=0;
        ListNode p = head;
        while(p!=null){
            length++;
            p = p.next;
        }
        if(k>length)
            return null;
        //System.out.println("length===="+length);
        int n = length-k+1;
        for (int i = 1; i < n; i++) {
            result = result.next;
        }
        return result;
    }
    //第二种办法  使用两个指针，
    /*
    * 一个指针先走k-1 步
    * 然后两个指针一起走，当先走的那个指针到链表末尾后，那个慢的指针走到的位置就是倒数第k个
    * 为什么？ ===> 先走k-1步，链表还剩下 n-(k-1)个结点，正数 (n-(k-1)) 就是倒数第k个
    * 要注意一些边界情况  防止空指针异常
    * */
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode first = head;
        ListNode second = head;
        if(first==null||k==0){
            return null;
        }
        for (int i = 0; i <k-1 ; i++) {
            if(first.next!=null){
                first = first.next;
            }else{
                return null;
            }
        }
        while(first.next!=null){
            second = second.next;
            first = first.next;
        }
        return second;
    }
}
